package demo.practice.competition;

import java.util.*;

public class P5861 {

    public static void main(String[] args) {
        P5861 p5861 = new P5861();
        p5861.maxTaxiEarnings(10, new int[][]{{5, 7, 1}, {8, 10, 7}, {6, 7, 9}, {3, 9, 2}, {7, 8, 6}, {8, 9, 6}, {8, 10, 10}, {9, 10, 4}, {9, 10, 7}, {6, 9, 2}});
    }

    //归并排序
    //由两个有序数组，合并成一个有序数组


    //快排
    //基准点划分法，基准点前面的比基准点小，后面的比基准点打


    public void quickSort() {

    }

    public void mergeSort(int[][] rides, int min, int max) {

        if (min >= max)
            return;
        int mid = min + (max - min) / 2;

        mergeSort(rides, min, mid);
        mergeSort(rides, mid + 1, max);

        int tmp[][] = new int[max - min + 1][3];
        int i = min;
        int j = mid + 1;

        for (int k = 0; k < tmp.length; k++) {
            int a1[] = i <= mid ? rides[i] : new int[]{Integer.MAX_VALUE, 0, 0};
            int a2[] = j <= max ? rides[j] : new int[]{Integer.MAX_VALUE, 0, 0};

            if (a1[0] < a2[0]) {
                i++;
                tmp[k] = a1;
            } else {
                j++;
                tmp[k] = a2;
            }
        }
        System.arraycopy(tmp, 0, rides, min, tmp.length);
    }

    //  Map<Integer, List<int[]>> map = new HashMap<>();


    public long maxTaxiEarnings(int n, int[][] rides) {
        Arrays.sort(rides, (a, b) -> a[1] - b[1]);

        //mergeSort(rides, 0, rides.length - 1);
        long dp[] = new long[rides.length];
        //dp[i]代表  第i的个二维数组的最大收益
        //dp[0]= 0
        //dp[i] =  dp[i-1]+(endi - starti + tipi)
        int[] f = rides[0];
        dp[0] = f[1] - f[0] + f[2];
        //map.put(0, new ArrayList<>(Arrays.asList(rides[0])));
        for (int i = 1; i < rides.length; i++) {
            int[] b = rides[i - 1];
            int[] t = rides[i];
            dp[i] = t[1] - t[0] + t[2];
            //List<int[]> ints = new ArrayList<>(Arrays.asList(rides[i]));
            for (int j = i - 1; j >= 0; j--) {
                if (rides[j][1] <= t[0]) {
                    dp[i] = Math.max(dp[j] + t[1] - t[0] + t[2], dp[i]);

                }
            }
        }

        long res = dp[0];
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(dp[i], res);
        }
        return res;
    }
}
